package com.rom.tree.HuffmanTree;

import java.util.*;

/**
 * @author YLNO
 * @version 1.0
 * @date 2023/12/14 14:29
 */
public class HuffmanCode {
    public static void main(String[] args) {

       String content = "i like like like java do you like a java";

//       [105, 32, 108, 105, 107, 101, 32, 108, 105, 107, 101, 32, 108, 105, 107, 101, 32, 106, 97, 118, 97, 32, 100, 111, 32, 121, 111, 117, 32, 108, 105, 107, 101, 32, 97, 32, 106, 97, 118, 97]
       byte[] contentBytes = content.getBytes();

        List<NNode> nodes = getNodes(contentBytes);
//        System.out.println(Arrays.toString(contentBytes));
//        System.out.println(nodes);
        for (NNode n:nodes) {
            System.out.println(n);
        }

        System.out.println("构建的huffman树----------------------->>>");
        NNode huffmanTreeRoot = createHuffmanTree(nodes);
        //前序遍历huffman树
        System.out.println("huffman遍历----------------------->>>");
        preOrder(huffmanTreeRoot);
        System.out.println("huffman编码----------------------->>>");
        getCodes(huffmanTreeRoot,"",new StringBuilder());
        System.out.println(huffmanCodes);
        for (Map.Entry<Byte,String> e: huffmanCodes.entrySet()) {
            System.out.println((char) e.getKey().byteValue()+"->"+e.getValue());
        }

        System.out.println();
    }

    //获取节点列表
    public static List<NNode> getNodes(byte[] bytes){

        Map<Byte,Integer> map = new HashMap<>();
        for(byte b : bytes){
            if(map.get(b)==null){
                map.put(b,1);
            }else{
                map.put(b,map.get(b)+1);
            }
        }
        ArrayList<NNode> nNodes = new ArrayList<>();
        //将Map构建成ArrayList Node
        for (Map.Entry<Byte,Integer> entry:map.entrySet()) {
            nNodes.add(new NNode(entry.getValue(), entry.getKey()));
        }

        return nNodes;
    }
    //创建huffmanTree树
    public static NNode createHuffmanTree(List<NNode> node){

        while (node.size() > 1){
            //排序
            Collections.sort(node);

//            取出最前面的两个
            NNode leftNode = node.remove(0);
            NNode rightNode = node.remove(0);

            NNode parent = new NNode(leftNode.getValue() + rightNode.getValue(), null);
            parent.setLeft(leftNode);
            parent.setRight(rightNode);

            node.add(parent);
        }
        return node.get(0);
    }
    //前序遍历
    public static void preOrder(NNode root){

        if(root!=null){
            root.preOrder();
        }else {
            System.out.println("Root为空");
        }
    }

    //保存编码
    static Map<Byte,String> huffmanCodes = new HashMap<>();
    //获取HuffManCode编码
    public static Map<Byte,String> getCodes(NNode root){


        return null;
    }

    public static void getCodes(NNode node,String code,StringBuilder stringBuilder){

        StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
        stringBuilder1.append(code);
        if(node!=null){
            if(node.getData() == null){
                //向左递归
                getCodes(node.getLeft(),"0",stringBuilder1);
                //向右递归
                getCodes(node.getRight(),"1",stringBuilder1);
            }else{
                huffmanCodes.put(node.getData(), stringBuilder1.toString());
            }
        }
    }
}

//节点//
class NNode implements Comparable<NNode>{

    private int value; //权重   出现的次数
    private Byte data; // 数据   a->105  ...
    //左右指针
    private NNode left;
    private NNode right;


    public void setValue(int value) {
        this.value = value;
    }

    public Byte getData() {
        return data;
    }

    public void setData(Byte data) {
        this.data = data;
    }

    public NNode(int value, Byte data) {
        this.value = value;
        this.data = data;
    }

    public int getValue() {
        return value;
    }



    public NNode getLeft() {
        return left;
    }

    public void setLeft(NNode left) {
        this.left = left;
    }



    @Override
    public String toString() {
        return "NNode{" +
                "value=" + value +
                ", data=" + data +
                '}';
    }


    public NNode getRight() {
        return right;
    }

    public void setRight(NNode right) {
        this.right = right;
    }

    @Override
    public int compareTo(NNode o) {
        //排序
        return this.value-o.value;
    }
    //前序遍历
    public void preOrder(){

        System.out.println(this);

        if(this.getLeft()!=null){
            this.getLeft().preOrder();
        }
        if(this.getRight()!=null){
            this.getRight().preOrder();
        }
    }
}
